/*
 * @lc app=leetcode.cn id=84 lang=typescript
 *
 * [84] 柱状图中最大的矩形
 */

// @lc code=start
function largestRectangleArea(heights: number[]): number {
  const m = heights.length;
  // 左边第一个比i元素小的位置
  const l = new Array(m).fill(-1);
  // 右边第一个比i元素小位置
  const r = new Array(m).fill(m);
  // 单调递增栈
  const stack: number[] = [];
  for (let i = 0; i < m; i++) {
    while (stack.length && heights[i] < heights[stack[stack.length - 1]]) {
      r[stack[stack.length - 1]] = i;
      stack.pop();
    }
    if (stack.length) l[i] = stack[stack.length - 1];
    stack.push(i);
  }

  let ans = 0;
  for (let i = 0; i < m; i++) {
    // 计算面积，高度*跨度
    ans = Math.max(ans, heights[i] * (r[i] - l[i] - 1));
  }

  return ans;
}
// @lc code=end
